#include "CKlotski.h"


int CKlotski::m_fnMove(int iSelect, int iPoint)
{
    int iResult;
    iResult = -1;
    switch (m_lpbtData[iSelect])
    {
    case 'o':
        if
        (
            (iSelect % 4 != 3 && iPoint == iSelect + 1) ||
            (iSelect % 4 != 0 && iSelect == iPoint + 1) ||
            (iSelect / 4 < 4 && iPoint == iSelect + 4) ||
            (iSelect / 4 > 0 && iSelect == iPoint + 4)
        )
        {
            m_lpbtData[iSelect] = ' ';
            m_lpbtData[iPoint] = 'o';
            iResult = iPoint;
        }
        break;
    case '^':
        if (iSelect / 4 > 0 && iPoint == iSelect - 4)
        {
            m_lpbtData[iSelect - 4] = m_lpbtData[iSelect];
            m_lpbtData[iSelect] = m_lpbtData[iSelect + 4];
            m_lpbtData[iSelect + 4] = ' ';
            iResult = iSelect - 4;
        }
        if (iSelect / 4 < 3 && iPoint == iSelect + 8)
        {
            m_lpbtData[iSelect + 8] = m_lpbtData[iSelect + 4];
            m_lpbtData[iSelect + 4] = m_lpbtData[iSelect];
            m_lpbtData[iSelect] = ' ';
            iResult = iSelect + 4;
        }
        if
        (
            (iSelect % 4 != 0 && ((iPoint == iSelect - 1) || (iPoint == iSelect + 3))) &&
            (m_lpbtData[iSelect - 1] == ' ' && m_lpbtData[iSelect + 3] == ' ')
        )
        {
            m_lpbtData[iSelect - 1] = m_lpbtData[iSelect];
            m_lpbtData[iSelect + 3] = m_lpbtData[iSelect + 4];
            m_lpbtData[iSelect] = ' ';
            m_lpbtData[iSelect + 4] = ' ';
            iResult = iSelect - 1;
        }
        if
        (
            (iSelect % 4 != 3 && ((iPoint == iSelect + 1) || (iPoint == iSelect + 5))) &&
            (m_lpbtData[iSelect + 1] == ' ' && m_lpbtData[iSelect + 5] == ' ')
        )
        {
            m_lpbtData[iSelect + 1] = m_lpbtData[iSelect];
            m_lpbtData[iSelect + 5] = m_lpbtData[iSelect + 4];
            m_lpbtData[iSelect] = ' ';
            m_lpbtData[iSelect + 4] = ' ';
            iResult = iSelect + 1;
        }
        break;
    case '<':
        if (iSelect % 4 != 0 && iPoint == iSelect - 1)
        {
            m_lpbtData[iSelect - 1] = m_lpbtData[iSelect];
            m_lpbtData[iSelect] = m_lpbtData[iSelect + 1];
            m_lpbtData[iSelect + 1] = ' ';
            iResult = iSelect - 1;
        }
        if (iSelect % 4 != 3 && iPoint == iSelect + 2)
        {
            m_lpbtData[iSelect + 2] = m_lpbtData[iSelect + 1];
            m_lpbtData[iSelect + 1] = m_lpbtData[iSelect];
            m_lpbtData[iSelect] = ' ';
            iResult = iSelect + 1;
        }
        if
        (
            (iSelect / 4 > 0 && ((iPoint == iSelect - 4) || (iPoint == iSelect - 3))) &&
            (m_lpbtData[iSelect - 4] == ' ' && m_lpbtData[iSelect - 3] == ' ')
        )
        {
            m_lpbtData[iSelect - 4] = m_lpbtData[iSelect];
            m_lpbtData[iSelect - 3] = m_lpbtData[iSelect + 1];
            m_lpbtData[iSelect] = ' ';
            m_lpbtData[iSelect + 1] = ' ';
            iResult = iSelect - 4;
        }
        if
        (
            (iSelect / 4 < 4 && ((iPoint == iSelect + 4) || (iPoint == iSelect + 5))) &&
            (m_lpbtData[iSelect + 4] == ' ' && m_lpbtData[iSelect + 5] == ' ')
        )
        {
            m_lpbtData[iSelect + 4] = m_lpbtData[iSelect];
            m_lpbtData[iSelect + 5] = m_lpbtData[iSelect + 1];
            m_lpbtData[iSelect] = ' ';
            m_lpbtData[iSelect + 1] = ' ';
            iResult = iSelect + 4;
        }
        break;
    case 'p':
        if
        (
            (iSelect % 4 != 0 && ((iPoint == iSelect - 1) || (iPoint == iSelect + 3))) &&
            (m_lpbtData[iSelect - 1] == ' ' && m_lpbtData[iSelect + 3] == ' ')
        )
        {
            m_lpbtData[iSelect - 1] = m_lpbtData[iSelect];
            m_lpbtData[iSelect + 3] = m_lpbtData[iSelect + 4];
            m_lpbtData[iSelect] = m_lpbtData[iSelect + 1];
            m_lpbtData[iSelect + 4] = m_lpbtData[iSelect + 5];
            m_lpbtData[iSelect + 1] = ' ';
            m_lpbtData[iSelect + 5] = ' ';
            iResult = iSelect - 1;
        }
        if
        (
            (iSelect % 4 < 2 && ((iPoint == iSelect + 2) || (iPoint == iSelect + 6))) &&
            (m_lpbtData[iSelect + 2] == ' ' && m_lpbtData[iSelect + 6] == ' ')
        )
        {
            m_lpbtData[iSelect + 2] = m_lpbtData[iSelect + 1];
            m_lpbtData[iSelect + 6] = m_lpbtData[iSelect + 5];
            m_lpbtData[iSelect + 1] = m_lpbtData[iSelect];
            m_lpbtData[iSelect + 5] = m_lpbtData[iSelect + 4];
            m_lpbtData[iSelect] = ' ';
            m_lpbtData[iSelect + 4] = ' ';
            iResult = iSelect + 1;
        }
        if
        (
            (iSelect / 4 > 0 && ((iPoint == iSelect - 4) || (iPoint == iSelect - 3))) &&
            (m_lpbtData[iSelect - 4] == ' ' && m_lpbtData[iSelect - 3] == ' ')
        )
        {
            m_lpbtData[iSelect - 4] = m_lpbtData[iSelect];
            m_lpbtData[iSelect - 3] = m_lpbtData[iSelect + 1];
            m_lpbtData[iSelect] = m_lpbtData[iSelect + 4];
            m_lpbtData[iSelect + 1] = m_lpbtData[iSelect + 5];
            m_lpbtData[iSelect + 4] = ' ';
            m_lpbtData[iSelect + 5] = ' ';
            iResult = iSelect - 4;
        }
        if
        (
            (iSelect / 4 < 3 && ((iPoint == iSelect + 8) || (iPoint == iSelect + 9))) &&
            (m_lpbtData[iSelect + 8] == ' ' && m_lpbtData[iSelect + 9] == ' ')
        )
        {
            m_lpbtData[iSelect + 8] = m_lpbtData[iSelect + 4];
            m_lpbtData[iSelect + 9] = m_lpbtData[iSelect + 5];
            m_lpbtData[iSelect + 4] = m_lpbtData[iSelect];
            m_lpbtData[iSelect + 5] = m_lpbtData[iSelect + 1];
            m_lpbtData[iSelect] = ' ';
            m_lpbtData[iSelect + 1] = ' ';
            iResult = iSelect + 4;
        }
        break;
    default:
        iResult = -1;
    }
    return iResult;
}

void CKlotski::m_fnGame(int iGameId)
{
    switch (iGameId)
    {
    case 1:
        strcpy(m_lpbtStart, "o  o^oo^_<>_^pq^_bd_");
        break;
    case 2:
        strcpy(m_lpbtStart, "^  ^_oo_o<>o^pq^_bd_");
        break;
    case 3:
        strcpy(m_lpbtStart, "^  ^_<>_oooo^pq^_bd_");
        break;
    case 4:
        strcpy(m_lpbtStart, "^  ^_oo_^<>^_pq_obdo");
        break;
    case 5:
        strcpy(m_lpbtStart, " <> ^^^^____opqoobdo");
        break;
    case 6:
        strcpy(m_lpbtStart, " <> o^^o^__^_pq_obdo");
        break;
    case 7:
        strcpy(m_lpbtStart, " <> o<>oo<>o^pq^_bd_");
        break;
    case 8:
        strcpy(m_lpbtStart, " <> o<>o^<>^_pq_obdo");
        break;
    case 9:
        strcpy(m_lpbtStart, "o  oo<>o<><>^pq^_bd_");
        break;
    default:
        break;
    }
}


void CKlotski::m_fnRestart()
{
    m_vecSolution.clear();
    strcpy(m_lpbtData, m_lpbtStart);
    m_iQueueSize = 0;
    m_iVertices = 0;
    m_iStep = 0;
}

int CKlotski::m_fnEnumMove(char *m_lpbtOriginal, char lplpbtChanged[8][24])
{
    int lpiVade[2], i, j;
    lpiVade[0] = lpiVade[1] = -1;
    for (i = 0; i < 20; ++i)
    {
        if (m_lpbtOriginal[i] == ' ')
        {
            if (lpiVade[0] == -1)
            {
                lpiVade[0] = i;
            }
            else
            {
                lpiVade[1] = i;
            }
        }
    }
    i = 0;
    for (j = 0; j < 2; ++j)
    {
        if (lpiVade[j] / 4 != 0 && m_lpbtOriginal[lpiVade[j] - 4] == 'o')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[j]] = 'o';
            lplpbtChanged[i][lpiVade[j] - 4] = ' ';
            ++i;
        }
        if (lpiVade[j] / 4 > 1 && m_lpbtOriginal[lpiVade[j] - 8] == '^')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[j]] = '_';
            lplpbtChanged[i][lpiVade[j] - 4] = '^';
            lplpbtChanged[i][lpiVade[j] - 8] = ' ';
            ++i;
        }
        if (lpiVade[j] / 4 < 4 && m_lpbtOriginal[lpiVade[j] + 4] == 'o')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[j]] = 'o';
            lplpbtChanged[i][lpiVade[j] + 4] = ' ';
            ++i;
        }
        if (lpiVade[j] / 4 < 3 && m_lpbtOriginal[lpiVade[j] + 4] == '^')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[j]] = '^';
            lplpbtChanged[i][lpiVade[j] + 4] = '_';
            lplpbtChanged[i][lpiVade[j] + 8] = ' ';
            ++i;
        }
        if (lpiVade[j] % 4 != 0 && m_lpbtOriginal[lpiVade[j] - 1] == 'o')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[j]] = 'o';
            lplpbtChanged[i][lpiVade[j] - 1] = ' ';
            ++i;
        }
        if (lpiVade[j] % 4 > 1 && m_lpbtOriginal[lpiVade[j] - 2] == '<')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[j]] = '>';
            lplpbtChanged[i][lpiVade[j] - 1] = '<';
            lplpbtChanged[i][lpiVade[j] - 2] = ' ';
            ++i;
        }
        if (lpiVade[j] % 4 < 3 && m_lpbtOriginal[lpiVade[j] + 1] == 'o')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[j]] = 'o';
            lplpbtChanged[i][lpiVade[j] + 1] = ' ';
            ++i;
        }
        if (lpiVade[j] % 4 < 2 && m_lpbtOriginal[lpiVade[j] + 1] == '<')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[j]] = '<';
            lplpbtChanged[i][lpiVade[j] + 1] = '>';
            lplpbtChanged[i][lpiVade[j] + 2] = ' ';
            ++i;
        }
    }
    if (lpiVade[0] / 4 < 4 && lpiVade[0] + 4 == lpiVade[1])
    {
        if (lpiVade[0] % 4 != 0 && m_lpbtOriginal[lpiVade[0] - 1] == '^')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[0]] = '^';
            lplpbtChanged[i][lpiVade[1]] = '_';
            lplpbtChanged[i][lpiVade[0] - 1] = ' ';
            lplpbtChanged[i][lpiVade[1] - 1] = ' ';
            ++i;
        }
        if (lpiVade[0] % 4 < 3 && m_lpbtOriginal[lpiVade[0] + 1] == '^')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[0]] = '^';
            lplpbtChanged[i][lpiVade[1]] = '_';
            lplpbtChanged[i][lpiVade[0] + 1] = ' ';
            lplpbtChanged[i][lpiVade[1] + 1] = ' ';
            ++i;
        }
        if (lpiVade[0] % 4 > 1 && m_lpbtOriginal[lpiVade[0] - 2] == 'p')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[0]] = 'q';
            lplpbtChanged[i][lpiVade[1]] = 'd';
            lplpbtChanged[i][lpiVade[0] - 1] = 'p';
            lplpbtChanged[i][lpiVade[1] - 1] = 'b';
            lplpbtChanged[i][lpiVade[0] - 2] = ' ';
            lplpbtChanged[i][lpiVade[1] - 2] = ' ';
            ++i;
        }
        if (lpiVade[0] % 4 < 2 && m_lpbtOriginal[lpiVade[0] + 1] == 'p')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[0]] = 'p';
            lplpbtChanged[i][lpiVade[1]] = 'b';
            lplpbtChanged[i][lpiVade[0] + 1] = 'q';
            lplpbtChanged[i][lpiVade[1] + 1] = 'd';
            lplpbtChanged[i][lpiVade[0] + 2] = ' ';
            lplpbtChanged[i][lpiVade[1] + 2] = ' ';
            ++i;
        }
    }
    else if (lpiVade[0] % 4 < 3 && lpiVade[0] + 1 == lpiVade[1])
    {
        if (lpiVade[0] / 4 != 0 && m_lpbtOriginal[lpiVade[0] - 4] == '<')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[0]] = '<';
            lplpbtChanged[i][lpiVade[1]] = '>';
            lplpbtChanged[i][lpiVade[0] - 4] = ' ';
            lplpbtChanged[i][lpiVade[1] - 4] = ' ';
            ++i;
        }
        if (lpiVade[0] / 4 < 4 && m_lpbtOriginal[lpiVade[0] + 4] == '<')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[0]] = '<';
            lplpbtChanged[i][lpiVade[1]] = '>';
            lplpbtChanged[i][lpiVade[0] + 4] = ' ';
            lplpbtChanged[i][lpiVade[1] + 4] = ' ';
            ++i;
        }
        if (lpiVade[0] / 4 > 1 && m_lpbtOriginal[lpiVade[0] - 8] == 'p')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[0]] = 'b';
            lplpbtChanged[i][lpiVade[1]] = 'd';
            lplpbtChanged[i][lpiVade[0] - 4] = 'p';
            lplpbtChanged[i][lpiVade[1] - 4] = 'q';
            lplpbtChanged[i][lpiVade[0] - 8] = ' ';
            lplpbtChanged[i][lpiVade[1] - 8] = ' ';
            ++i;
        }
        if (lpiVade[0] % 4 < 3 && m_lpbtOriginal[lpiVade[0] + 4] == 'p')
        {
            strcpy(lplpbtChanged[i], m_lpbtOriginal);
            lplpbtChanged[i][lpiVade[0]] = 'p';
            lplpbtChanged[i][lpiVade[1]] = 'q';
            lplpbtChanged[i][lpiVade[0] + 4] = 'b';
            lplpbtChanged[i][lpiVade[1] + 4] = 'd';
            lplpbtChanged[i][lpiVade[0] + 8] = ' ';
            lplpbtChanged[i][lpiVade[1] + 8] = ' ';
            ++i;
        }
    }
    return i;
}

int CKlotski::m_fnSolve()
{
    CCourseElement element;
    char lplpMoveStatus[8][24];
    int i, n;
    m_bSolving = true;
    //std::ofstream ofs("./Data.txt");
    std::queue<GraphVertex*> quvtSeed;
    CGraph graphSolver;
    GraphVertex *lpSeed, *lpVertex, *lpFinal;
    GraphEdge *edge0, *edge1;
    std::vector<GraphVertex*> buffer;
    m_iStep = 0;
    lpFinal = NULL;
    graphSolver.add_vertex(m_lpbtData);
    lpSeed = &(*(graphSolver.vertices.begin()));
    lpSeed->iInd = 0;
    quvtSeed.push(lpSeed);
    while (!quvtSeed.empty() && m_bSolving)
    {
        lpSeed = quvtSeed.front();
        quvtSeed.pop();
        n = m_fnEnumMove(lpSeed->m_lpbtData, lplpMoveStatus);
        for (i = 0; i < n; ++i)
        {
            //lpVertex = graphSolver.search_vertex(lpSeed, lplpMoveStatus[i]);
            lpVertex = graphSolver.round_search(lpSeed, lplpMoveStatus[i]);
            if (lpVertex == NULL)
            {
                lpVertex = graphSolver.range_search(lplpMoveStatus[i], lpSeed->iInd - 1);
            }
            if (lpVertex == NULL)
            {
                lpVertex = graphSolver.add_vertex(lplpMoveStatus[i]);
                strcpy(m_lpbtData, lpVertex->m_lpbtData);
                lpVertex->iInd = lpSeed->iInd + 1;
                quvtSeed.push(lpVertex);
                if (lpVertex->m_lpbtData[1] == 'p')
                {
                    lpFinal = lpVertex;
                    while (!quvtSeed.empty())
                    {
                        quvtSeed.pop();
                    }
                }
            }
            else
            {
                if (lpSeed->iInd + 1 < lpVertex->iInd)
                {
                    lpVertex->iInd = lpSeed->iInd + 1;
                }
            }
            graphSolver.add_edge(lpSeed, lpVertex);
        }
        m_iVertices = graphSolver.vertices.size();
        m_iQueueSize = quvtSeed.size();
    }
    n = 0;
    m_vecSolution.clear();
    if (lpFinal != NULL)
    {
        lpVertex = lpFinal;
        while (lpVertex->iInd != 0)
        {
            lpSeed = NULL;
            buffer.push_back(lpVertex);
            edge0 = lpVertex->edge->opps;
            edge1 = edge0;
            do
            {
                if (edge1->vertex->iInd == lpVertex->iInd - 1)
                {
                    lpSeed = edge1->vertex;
                }
                edge1 = edge1->opps->next;
            } while (edge1 != edge0 && lpSeed == NULL);
            lpVertex = lpSeed;
        }
        strcpy(m_lpbtData, lpVertex->m_lpbtData);
        strcpy(element.m_lpbtData, lpVertex->m_lpbtData);
        m_vecSolution.push_back(element);
        while(!buffer.empty())
        {
            lpVertex = *(buffer.rbegin());
            strcpy(element.m_lpbtData, lpVertex->m_lpbtData);
            m_vecSolution.push_back(element);
            buffer.pop_back();
        }
        n = lpFinal->iInd;
    }
    m_bSolving = false;
    return n;
}
